Referring to FIG. 1, typically, when a user (Alice) authenticates through a web-application to a server, they are presented with a dialog box within their browser window into which they enter a username and password. The username and password are sent from the web client to the server where they are authenticated. In most cases the credentials are transferred from the client to the server using http. As such, they are prone to being intercepted an attacker. If security is needed, an https protocol can be used. However, the credentials are still sent through the Internet and servers are able to read them.
Asymmetric cryptography offers secure distributed authentication schemes over insecure communication channels. However, users are required to provide public and private key-pairs or digital certificates; and the certificate must be installed for a web browser. This is not an easy task for beginners nor might it be possible if the user is operating a browser from a restricted client such as an Internet café.
Goldwasser, Micali, and Rackoff, “The knowledge complexity of interactive proof-systems”, STOC '85: Proceedings of the seventeenth annual ACM symposium on Theory of computing, pages 291-304, New York, N.Y., USA, 1985, ACM Press, discloses ZKP challenge-response authentication protocols, in which a prover proves his identity to a verifier, but the verifier is unable to compute the prover's secret using any received data.
The prerequisite for the protocol is that a user, for instance Alice, has to register her name and a public key and only those credentials are accessible to the verifier. Alice somehow maintains a private key, and the public-private key-pair depends on an NP problem on which the protocol is based. Referring now to FIG. 2, a typical ZKP authentication protocol operates as follows:                Step 1—Alice generates a random problem R and she computes f(R) using a one way hash function. The problem and the function are specific for the NP problem the protocol uses.        Step 2—She sends f(R) to the server where she wants to be authenticated. She keeps R secret.        Step 3—The server stores the received f(R) function and sends a request to Alice. The request contains a challenge. The, challenge is a random decision that requires Alice to be capable of answering one of two questions: one of which demonstrates her knowledge of the private key (f(R, private key)); and the other, an easy question, to prevent her from cheating (R).        Step 4—Alice sends back the answer that depends on the challenge: f(R, private key) or R. She always reveals only one parameter.        Step 5—The server verifies her answer. If the answer is correct, the server can authenticate her or she can be queried for another challenge to decrease the probability of cheating; and thus, loop back to Step 1.        
In the above protocol, Step 1 is also called witness, Steps 2 and 3 are challenge, whereas step 4 is response. If the protocol is repeated t times, all t rounds must be answered successfully to prove Alice's identity. The server is always convinced with probability 1-2−t. In zero-knowledge proof protocols, the verifier cannot learn anything from the authentication procedure. Moreover, the verifier is unable to cheat the prover because of having always only one value R or f(R, private key); this is not sufficient to calculate the prover's secret. Furthermore, the verifier cannot cheat the prover because the protocol is repeated as long as the verifier is not convinced; due to random challenge selection, the verifier cannot pretend to be the prover to a third party.
Typically, ZKP challenge-response protocols arc based on: the discrete logarithm problem, the square-root problem, or elliptical curve cryptography.
The discrete logarithm problem is defined as finding x such thatgx=b mod nwhere g, b, and n are known for both the prover and verifier and x must be coprime to n.
In the square-root problem, Alice wants to prove that she knows such an x thatx2=b mod nfor known b, and n and where x must be co-prime to n.
In Elliptic curve cryptography (ECC) a public-private key-par on an elliptic curve is defined as:y2=x3+ax+b where 4a3+27b2≠0, and relies on a complexity of point multiplication over such a curve.
Nonetheless, in each of the above cases, the user's private key must either be available on a local machine from which they are trying to authenticate themselves, or the user must allow their password to be transmitted across a network. The former makes a ZKP implementation based on the above problems infeasible within a browser, while the latter is undesirable.
It is an object of the present invention to provide a more secure form of authentication while preserving the ease of use of simplistic username/password systemS within a web-browser application.